/*
 * @lc app=leetcode.cn id=1514 lang=typescript
 *
 * [1514] 概率最大的路径
 */

// @lc code=start

//  思想：Dijkstra
//  参考：https://labuladong.github.io/algo/2/17/34/

function maxProbability(n: number, edges: number[][], succProb: number[], start: number, end: number): number {
    interface State {
        val: number
        // 从 start 节点到达当前节点的概率
        probFromStart: number
    }

    // 创建邻接表
    const graph: State[][] = []
    for (let i = 0; i < n; i++) {
        graph[i] = []
    }
    for (let i = 0; i < edges.length; i++) {
        const from = edges[i][0], to = edges[i][1], prob = succProb[i]
        graph[from].push({ val: to, probFromStart: prob })
        graph[to].push({ val: from, probFromStart: prob })
    }
    // dp table 初始化为一个取不到的最小值
    const probTo: number[] = new Array(graph.length).fill(-1)
    // base case，start 到 start 的概率就是 1
    probTo[start] = 1
    // 从起点 start 开始进行 BFS
    const queue: State[] = [{ val: start, probFromStart: 1 }]

    while (queue.length > 0) {
        const curr = queue.shift()
        const currVal = curr!.val, currProb = curr!.probFromStart
        // 遇到终点提前返回
        if (currVal === end) {
            continue
        }
        // 到达当前节点的概率与dp值比较，dp保证为小值
        if (currProb > probTo[currVal]) {
            continue
        }
        // 将 curNode 的相邻节点装入队列
        for (const neighbor of graph[currVal]) {
            const nextVal = neighbor.val
            const nextProb = probTo[currVal] * neighbor.probFromStart
            if (probTo[nextVal] < nextProb) {
                probTo[nextVal] = nextProb
                queue.push({
                    val: nextVal, probFromStart: nextProb
                })
            }
        }
    }
    return probTo[end] === -1 ? 0 : probTo[end]
};
// @lc code=end

console.log(maxProbability(3, [[0, 1], [1, 2], [0, 2]], [0.5, 0.5, 0.2], 0, 2))
console.log(maxProbability(3, [[0, 1], [1, 2], [0, 2]], [0.5, 0.5, 0.2], 0, 2))
console.log(maxProbability(3, [[0, 1]], [0.5], 0, 2))
